import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Text {
    //最小 k 个数 ---> 用小根堆来实现
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int x:arr) {
            minHeap.offer(x);
        }
        // 1） 小根堆当中已经将所有数组的元素存储起来了
        // 2) 依次弹出 k 个元素即为所求,将弹出的元素全部放进数组里面 再返回
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }
    // 最小 k 个数 ---> 法二
    public int[] smallestK1(int[] arr, int k){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Imp());
        // 1) 前 k 个元素 制成大跟堆
        for (int i = 0; i < k; k++) {
            maxHeap.offer(arr[i]);
        }
        // 2) 后面的元素依次与堆顶元素进行比较
        for (int i = k; i < arr.length; i++) {
            // 获取栈顶元素
            int top = maxHeap.peek();
            // 比较
            // 如果栈顶元素大就出，并且进数，不大就继续比较下一个数
            if(top>arr[k]){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        // 3) 将最后的堆里面的元素放进一个数组里面，并返回
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }
    public static void main(String[] args) {
        //
    }
    //堆接口 PriorityQueue 的实现，比较器
    public static void main1(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);
        priorityQueue1.poll();
    }
}
class Imp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1,Integer o2) {
        return o2-o1;
    }
}
